package 数组;

/**
 * @author: 大怪
 * @email: 962527441@qq.com
 */

/**
 * 题目：
 * 给定一个二维矩阵 matrix，以下类型的多个请求：
 * 计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。
 * 实现 NumMatrix 类：
 * NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
 * int sumRegion(int row1, int col1, int row2, int col2) 返回左上角 (row1, col1) 、右下角 (row2, col2) 的子矩阵的元素总和。
 *
 *
 *
 */
public class 二维子矩阵的和 {
    class NumMatrix {

        int[][] tmp;
        public NumMatrix(int[][] matrix) {
            tmp = new int[matrix.length+1][matrix[0].length+1];
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix[0].length; j++) {
                    tmp[i+1][j+1] = tmp[i+1][j]+tmp[i][j+1]+matrix[i][j]-tmp[i][j];
                }
            }
        }

        public int sumRegion(int row1, int col1, int row2, int col2) {
            return tmp[row2+1][col2+1]-tmp[row2+1][col1]-tmp[row1][col2+1]+tmp[row1][col1];
        }
    }
}
